home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group98a.txt / 000144_icon-group-sender _Tue Mar 17 16:26:20 1998.msg < prev    next >
Internet Message Format  |  2000-09-20  |  2KB
  1. Return-Path: <icon-group-sender>
  2. Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
  3.     by baskerville.CS.Arizona.EDU (8.8.7/8.8.7) with SMTP id QAA08544
  4.     for <icon-group-addresses@baskerville.CS.Arizona.EDU>; Tue, 17 Mar 1998 16:26:20 -0700 (MST)
  5. Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
  6.     id AA17517; Tue, 17 Mar 1998 16:26:19 -0700
  7. Message-Id: <199803172152.OAA16672@orpheus.gemini.edu>
  8. From: swampler@noao.edu (Steve Wampler)
  9. Date: Tue, 17 Mar 1998 14:52:34 MST
  10. In-Reply-To: Mark Evans's mail message of Mar 13,  4:06pm.
  11. X-Mailer: Mail User's Shell (7.2.3 5/22/91)
  12. To: icon-group@optima.CS.Arizona.EDU
  13. Subject: Re: Letter Probabilities
  14. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  15. Status: RO
  16. Content-Length: 1502
  17.  
  18.  
  19. On Mar 17 at 10:16am, Mark Evans writes:
  20. } I think that we have here one of those classic execution-time vs.
  21. } memory-space tradeoffs that they teach about in computer science
  22. } classes.
  23. }
  24. } Mark
  25. }
  26. } Paul Abrahams wrote:
  27. } >
  28. } > Using the probabilities to construct a weighted string and then
  29. } > selecting a random character from the string does have one unaesthetic
  30. } > property, in my book: the length of the string grows exponentially with
  31. } > the precision of the probabilities.  For that reason I'd opt for a
  32. } > binary search, which takes 5 probes no matter what the precision.
  33. } >
  34. } > I wonder if there's another way of attacking this problem.
  35.  
  36.  
  37. I'm not sure I understand this.  The upper bound on the weighted string
  38. is the length of the input text itself.  In fact, the input text
  39. itself is the *perfect* weighted string!  There is no need to reduce
  40. the string to probabilities and then expand the probabilities back
  41. into a different string - all this does is (a) slow things down and
  42. (b) reduce the 'accuracy' of the probabilities.  ((b) isn't all that
  43. important when producing 'random' text, I suppose.)
  44.  
  45. Now, for *really, really* large input samples, this becomes
  46. inefficent (memory-wise).  It's certainly not an issue for the
  47. 20K character lengths I've seen mentioned here.  I regularly
  48. process 10-MB strings with Icon.
  49.  
  50.  
  51. -- 
  52. Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)]
  53. The gods that smiled at your birth are now laughing openly. (Fortune Cookie)
  54.